package com.mzy.linear_struct.hot100.动态规划;


/**
 * @Author: mizy3
 * @Date: 2024/08/11/下午9:51
 * @Description:
 */
public class Pro62不同路径 {

    private int uniquePaths(int m, int n) {
        // dp[i][j] 表示 i、j位置有多少种走法
        int[][] dp = new int[m][n];

        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }

        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }


    /*public int uniquePaths(int m, int n) {
        // m 是纵轴，n是横轴
        // 确认 dp数组，dp[i][j]
        int[][] dp = new int[m][n];
        // 确认递推方程 dp[i - 1][j] + dp[i][j - 1]
        // 初始化dp
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
*/
    public static void main(String[] args) {
        System.out.println(new Pro62不同路径().uniquePaths(3, 2));
    }



  /*  private int uniquePaths(int m, int n) {
        // m纵坐标，n横坐标 dp[m][n] 表示走到当前路径有多少种走法
        int[][] dp = new int[m][n];

        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }

        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = 1;
        }

        // dp[i][j] = dp[i][j - 1] + dp[i - 1][j]

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }

        return dp[m - 1][n - 1];
    }
*/
   /* private int uniquePaths(int m, int n) {
        // m 纵坐标，n 横坐标
        // m、n表示当前位置，dp[m][n] 表示当前位置总共有多少种走法
        int[][] dp = new int[m][n];

        // dp[i][j] = d[i - 1][j] + dp[i][j - 1]

        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < dp[j].length; j++) {
            dp[0][j] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }


        return dp[m - 1][n - 1];
    }*/
}
